﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream> 
#include<cstdlib>  
#include<vector>
#include<list>
#include<queue>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>




using namespace std;







//int N, K;
//char map[100][100];//点的图案的记录
//int map_record[100][100];//点的记录
//int map_steps[100][100];//步数的记录
//int Sx, Sy;//起点位置
//int Gx, Gy;//终点位置
////宝藏位置
//int map_x[20];
//int map_y[20];
//void clear()
//{
//	for (int i = 0; i < N; i++)
//	{
//		for (int j = 0; j < N; j++)
//		{
//			map_record[i][j] = 0;
//			map_steps[i][j] = 10000;
//		}
//	}
//}
//void Exame(int x, int y, int nextX, int nextY, queue<int>& a, queue<int>& b)
//{
//	if (map[nextX][nextY] == '#' || map_record[nextX][nextY] == 1 || nextX < 0 || nextY < 0 || nextX >= N || nextY >= N)//不记录
//	{
//		//此路不通,要么超出界限，要么为围墙，要么已经走过了
//	}
//	else if (map[nextX][nextY] == '@' || map[nextX][nextY] == 'S' || map[nextX][nextY] == 'G')//+1
//	{
//		a.push(nextX);
//		b.push(nextY);
//		//不可达——#
//		//可达——@/S/G/a/b/c……
//		//@/S/G——1分钟
//		//a/b/c……2分钟
//		if (map_steps[nextX][nextY] > map_steps[x][y] + 1)
//		{
//			map_steps[nextX][nextY] = map_steps[x][y] + 1;
//		}
//	}
//	else//+2
//	{
//		a.push(nextX);
//		b.push(nextY);
//		if (map_steps[nextX][nextY] > map_steps[x][y] + 2)
//		{
//			map_steps[nextX][nextY] = map_steps[x][y] + 2;
//		}
//	}
//}
//int BFS(int startX, int startY, int endX, int endY)//寻找以start为起点，end为结尾的最短路径
//{
//	clear();//记录先清零
//	//记录现在可能的坐标
//	int x = startX;
//	int y = startY;
//	int nextX;
//	int nextY;
//	//记录需要遍历的坐标
//	queue<int>traverseX;
//	queue<int>traverseY;
//	//放入第一个需要遍历的首个坐标
//	traverseX.push(x);
//	traverseY.push(y);
//	map_record[x][y] = 1;//已标记
//	map_steps[x][y] = 0;//步数记录
//	int num = 0;
//	while (!traverseX.empty() && num < 100000)
//	{
//		//当前位置
//		x = traverseX.front();
//		y = traverseY.front();
//		//上下左右广度优先遍历
//		//上
//		nextX = x - 1;
//		nextY = y;
//		Exame(x, y, nextX, nextY, traverseX, traverseY);
//		//下
//		nextX = x + 1;
//		nextY = y;
//		Exame(x, y, nextX, nextY, traverseX, traverseY);
//		//左
//		nextX = x;
//		nextY = y - 1;
//		Exame(x, y, nextX, nextY, traverseX, traverseY);
//		//右
//		nextX = x;
//		nextY = y + 1;
//		Exame(x, y, nextX, nextY, traverseX, traverseY);
//		//操作
//		traverseX.pop();
//		traverseY.pop();
//		map_record[x][y] = 1;
//		num++;
//	}
//	return map_steps[endX][endY];
//}
//int findMinLoad_BFS(int K)//需要找到K个宝藏才可以
//{
//	int num = 0;//找到的宝藏数量
//	int steps = 0;
//	int nowX = Sx;
//	int nowY = Sy;
//	int nextX;
//	int nextY;
//	while (num < K)//当还没找到
//	{
//		nextX = map_x[num];
//		nextY = map_y[num];
//		steps += BFS(nowX, nowY, nextX, nextY);
//		num++;
//		nowX = nextX;
//		nowY = nextY;
//	}
//	nextX = Gx;
//	nextY = Gy;
//	steps += BFS(nowX, nowY, nextX, nextY);
//	return steps;
//}
//
//
//int main()
//{
//	cin >> N >> K;
//	for (int i = 0; i < N; i++)
//	{
//		for (int j = 0; j < N; j++)
//		{
//			cin >> map[i][j];
//			if (map[i][j] >= 'a' && map[i][j] <= 't')
//			{
//				map_x[(int)map[i][j] - 97] = i;
//				map_y[(int)map[i][j] - 97] = j;
//			}
//			else if (map[i][j] == 'S')//记录起点位置
//			{
//				Sx = i;
//				Sy = j;
//			}
//			else if (map[i][j] == 'G')//记录终点位置
//			{
//				Gx = i;
//				Gy = j;
//			}
//		}
//	}
//	cout << findMinLoad_BFS(K);
//	return 0;
//}

struct State {
	int x, y;
	int state;
	int cost;
	State(int _x, int _y, int _state, int _cost) : x(_x), y(_y), state(_state), cost(_cost) {}
};

struct ComGreater
{
	bool operator()(State s1, State s2)
	{
		return s1.state > s2.state;
	}
};

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

int maze_explore(int n, int k, vector<string>& maze) {
	//起点、终点
	pair<int, int> start, end;
	//宝藏
	vector<pair<int, int>> treasures(k);
	int treasure_index = 0;
	//初始化
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (maze[i][j] == 'S') start = { i, j };
			else if (maze[i][j] == 'G') end = { i, j };
			else if ('a' <= maze[i][j] && maze[i][j] <= 'a' + k - 1) {
				treasures[treasure_index++] = { i, j };
			}
		}
	}

	const int INF = INT_MAX;
	vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(1 << k, INF)));
	dp[start.first][start.second][0] = 0;

	priority_queue<State, vector<State>, ComGreater> pq;
	pq.push(State(start.first, start.second, 0, 0));

	//状态转移
	while (!pq.empty()) {
		State cur = pq.top();
		pq.pop();
		if (cur.cost > dp[cur.x][cur.y][cur.state]) continue;
		if (cur.x == end.first && cur.y == end.second && cur.state == (1 << k) - 1) return cur.cost;

		for (int i = 0; i < 4; ++i) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < n && maze[nx][ny] != '#') {
				int new_state = cur.state;
				int idx = -1;
				for (int j = 0; j < k; ++j) {
					if (treasures[j].first == nx && treasures[j].second == ny) {
						idx = j;
						break;
					}
				}
				if (idx != -1 && !(cur.state & (1 << idx))) {
					new_state |= (1 << idx);
				}
				int new_cost = cur.cost + 1;
				if (idx != -1) new_cost += 1;
				if (new_cost < dp[nx][ny][new_state]) {
					dp[nx][ny][new_state] = new_cost;
					pq.push(State(nx, ny, new_state, new_cost));
				}
			}
		}
	}
	return -1;
}

int main() {
	int n, k;
	cin >> n >> k;
	vector<string> maze(n);
	for (int i = 0; i < n; ++i) {
		cin >> maze[i];
	}
	int result = maze_explore(n, k, maze);
	cout << result << endl;
	return 0;
}


//4.
// 7-4 跳一跳 (升级版)
//分数 15
//作者 Drizzle
//单位 山东科技大学
//我跳累了~😢
//
//人活着本没有意义，但只有活着就会碰到很多有趣的事，就像你发现了花，而我发现了你一样。
//这里有一段整数数组nums，你一开始处于下标为0的第一个元素处，请求出你最少跳几次能到达数组的末尾位置。
//
//当你在i位置时可以跳跃到以下三个位置：
//
//i + 1：i + 1 < nums.length
//	i - 1：i - 1 >= 0
//	j：nums[i] == nums[j]
//////////////////////////////////////


int jump(vector<int>& nums) {
	int n = nums.size();

	//队列，存储下标和操作步数
	queue<pair<int, int>> q;
	//访问表
	unordered_set<int> visited;
	// 使用哈希表记录每个值对应的位置列表
	//            数值     位置
	unordered_map<int, vector<int>> valueToIndices;
	for (int i = 0; i < n; ++i) {
		//插入值的位置
		valueToIndices[nums[i]].push_back(i);
	}
	q.push({ 0, 0 });
	visited.insert(0);
	while (!q.empty()) {
		int index = q.front().first;
		int steps = q.front().second;
		q.pop();
		//到达末尾返回步数
		if (index == n - 1) return steps;
		// 尝试向右跳
		if (index + 1 < n && visited.find(index + 1) == visited.end()) {
			visited.insert(index + 1);
			q.push({ index + 1, steps + 1 });
		}
		// 尝试向左跳
		if (index - 1 >= 0 && visited.find(index - 1) == visited.end()) {
			visited.insert(index - 1);
			q.push({ index - 1, steps + 1 });
		}
		// 从哈希表中获取相同值的位置
		if (valueToIndices.find(nums[index]) != valueToIndices.end()) {
			for (int j : valueToIndices[nums[index]]) {
				if (j != index && visited.find(j) == visited.end()) {
					visited.insert(j);
					q.push({ j, steps + 1 });
				}
			}
		}
	}
	return -1;
}


//int jump(std::vector<int>& nums) {
//	int n = nums.size();
//	
//
//	//队列，存储下标和操作步数
//	std::queue<std::pair<int, int>> q;
//	//访问表
//	std::unordered_set<int> visited;
//
//	q.push({ 0, 0 });
//	visited.insert(0);
//	while (!q.empty()) {
//		int index = q.front().first;
//		int steps = q.front().second;
//		q.pop();
//		//到达末尾返回步数
//		if (index == n - 1) return steps;
//		// 尝试向右跳
//		if (index + 1 < n && visited.find(index + 1) == visited.end()) {
//			visited.insert(index + 1);
//			q.push({ index + 1, steps + 1 });
//		}
//		// 尝试向左跳
//		if (index - 1 >= 0 && visited.find(index - 1) == visited.end()) {
//			visited.insert(index - 1);
//			q.push({ index - 1, steps + 1 });
//		}
//		// 尝试跳到相同值的位置
//		for (int j = 0; j < n; j++) {
//			if (nums[index] == nums[j] && j != index && visited.find(j) == visited.end()) {
//				visited.insert(j);
//				q.push({ j, steps + 1 });
//			}
//		}
//	}
//
//
//	//队列为空还没有返回，不能到达末尾
//	return -1;
//}

int main4() {
	int n;
	std::cin >> n;
	std::vector<int> nums;
	for (int i = 0; i < n; ++i) {
		int num;
		std::cin >> num;
		nums.push_back(num);
	}
	int result = jump(nums);
	std::cout << result << std::endl;
	return 0;
}


//3
//7 - 3 最小生成树 - kruskal算法
//分数 15
//作者 唐艳琴
//单位 中国人民解放军陆军工程大学
//某地对偏远地区实行“村村通”工程，目标是使整个地区任何两个村落间都可以实现快速交通
// （但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到拟修建道路的费用，
// 现请你编写程序，计算出全地区畅通需要的最低成本。
/// <summary>
/// /////////////////////////////////////////////////////////
/// </summary>
const int MaxVexNum = 100;
bool visited[MaxVexNum];
//边
struct Edge
{
	int _u;
	int _v;
	int _weight;
	Edge(int u, int v, int weight)
		:_u(u)
		, _v(v)
		, _weight(weight)
	{

	}
};

//用于查找每个节点的根
vector<int> parent(MaxVexNum);
//小顶堆的比较方式
class Compare_greater
{
public:
	bool operator()(Edge a, Edge b)
	{
		return a._weight > b._weight;
	}
};

//查找节点的根，用于检查是否处于同一个连通分量
int Find(int i)
{
	//若此点的父为自己，则还没有进入连通分量
	if (parent[i] == i)return i;
	//若此点的父为其他点，继续找父的父并更新
	return parent[i] = Find(parent[i]);
}
struct NodeRoad
{
	int _u;
	int _v;
	int _weight;
};

int main3()
{
	int n, m;
	priority_queue < Edge, vector<Edge>, Compare_greater> he;
	cin >> n >> m;
	vector<bool> visited(n + 1, false);
	vector<NodeRoad> resv;
	int total_weight = 0;
	int i, j, k;

	for (int x = 0; x < m; ++x)
	{
		cin >> i >> j >> k;
		he.emplace(i, j, k);
	}

	for (int i = 1; i <= n; ++i)
	{
		parent[i] = i;
	}

	while (!he.empty())
	{
		Edge e = he.top();
		he.pop();

		//若找到他们的父相同，则他们处于同一个连通分量，加上此边就会闭环,不加此边
		if (Find(e._v) != Find(e._u))
		{
			if (Find(e._v) != Find(e._u))
				parent[Find(e._v)] = Find(e._u);

			visited[e._u] = true;
			visited[e._v] = true;
			resv.push_back({ e._u, e._v,e._weight });
			total_weight += e._weight;
		}

	}

	/*for (int i = 1; i <= n; ++i)
	{
		if (visited[i] == false)
		{
			cout << -1;
			return 0;
		}
	}*/


	for (int i = 0; i < resv.size(); ++i)
	{
		cout << resv[i]._u << ',' << resv[i]._v << ',' << resv[i]._weight;
		cout << endl;
	}
	//cout << total_weight;
	////输出测试
	//for (int i = 0; i < m; ++i)
	//{
	//	cout << he.top()._u << ' ' << he.top()._v << ':' << he.top()._weight << endl;
	//	he.pop();
	//}

	return 0;
}





//2
//7-2 连通数
//分数 15
//作者 tan60
//单位 兰州大学
//度量一个有向图连通情况的一个指标是连通数，指图中可达顶点对的个数。
//在右图中，顶点1可以到达 1、2、3、4、5;
//顶点 2 可以到达 2、3、4、5;
//顶点 3 可以到达 3、4、 5:
//顶点 4、5 均只能达到自身，所以它的连通数为 14。
//请编写一个程序，输入一个图，求它的连通数。
/// <summary>
/// //////////////////////////////////////////////////////////////////////////
/// </summary>
/// <param name="v"></param>
/// <param name="graph"></param>
/// <param name="visited"></param>
/// 
/// 
/// 

//const int M = 2100;
//int head[M], h[M], r[M];
//int top, tim, cnt, patt;
//int blg[M], has[M];
//int mark[M][M];
//int n, ans, block, num, pat;
//int dfn[M], low[M];
//int stk[M], in[M];
//
//char ch[M];
//struct edge {
//	int to, next;
//}e[M * M], ed[M * M];
//inline void add(int u, int v) {
//	++pat; e[pat].to = v; e[pat].next = head[u]; head[u] = pat;
//}
//
//void tarjan(int u)  //缩点
//{
//	dfn[u] = low[u] = ++tim;
//	stk[++top] = u, in[u] = 1;
//	for (int i = head[u]; i; i = e[i].next) {
//		int v = e[i].to;
//		if (!dfn[v])
//			tarjan(v),
//			low[u] = min(low[u], low[v]);
//		else if (in[v])
//			low[u] = min(low[u], dfn[v]);
//	}
//	if (low[u] == dfn[u]) {
//		int now; ++cnt;
//		do {
//			now = stk[top--];
//			blg[now] = cnt;
//			++has[cnt];
//			in[now] = 0;
//		} while (now != u);
//	}
//}
//
//inline void addedge(int u, int v) {  //新图建边
//	++patt; ed[patt].to = v; ed[patt].next = h[u]; h[u] = patt;
//}
//inline void rebuild()
//{
//	for (int u = 1; u <= n; ++u)
//		for (int i = head[u]; i; i = e[i].next) {
//			int v = e[i].to;
//			if (blg[u] != blg[v])
//				addedge(blg[v], blg[u]),
//				++r[blg[u]];  //反向建图的操作
//		}
//}
//
//int main()
//{
//	scanf("%d", &n);
//	block = 30; num = n / block + 1;  //类似分块
//	for (int i = 1; i <= n; ++i) {
//		scanf("%s", ch + 1);
//		for (int j = 1; j <= n; ++j)
//			if (ch[j] - '0') add(i, j);
//	}
//	for (int i = 1; i <= n; ++i)
//		if (!dfn[i]) tarjan(i);
//	rebuild(); top = 0;
//	for (int i = 1; i <= n; ++i)  //对于每一个连通块内的点进行记录
//		mark[blg[i]][i / block + 1] |= (1 << (i % block));
//	for (int i = 1; i <= cnt; ++i)  //从入度为零的联通块开始操作
//		if (!r[i]) stk[++top] = i;
//	while (top) {
//		int u = stk[top]; --top;
//		for (int i = h[u]; i; i = ed[i].next) {
//			int v = ed[i].to;
//			for (int j = 1; j <= num; ++j)  //给指向的联通块加上自己已有的信息（分块加）
//				mark[v][j] |= mark[u][j];
//			if (--r[v] == 0) stk[++top] = v;
//		}
//	}
//	for (int i = 1; i <= cnt; ++i)  //每个连通块所能通到的点*联通块内点数，计入答案
//		for (int j = 1; j <= n; ++j)
//			if ((mark[i][j / block + 1]) & (1 << (j % block)))
//				ans += has[i];
//	printf("%d", ans);
//	return 0;
//}


void dfs(int v, const vector<vector<char>>& graph, vector<bool>& visited) {
	//可以到达自己
	visited[v] = true;
	for (int i = 0; i < graph.size(); ++i) {
		//如果可到达，继续搜索其可到达的点
		if (graph[v][i] == '1' && !visited[i]) {
			dfs(i, graph, visited);
		}
	}
}

int countConnectedPairs(const vector<vector<char>>& graph) {
	int n = graph.size();
	int count = 0;
	//深度优先搜索i的连通数
	for (int i = 0; i < n; ++i) {
		//每次初始化访问数组全为false
		vector<bool> visited(n, false);
		dfs(i, graph, visited);

		//记录连通数
		for (int j = 0; j < n; ++j) {
			if (visited[j]) {
				count++;
			}
		}
	}
	return count;
}

int main2() {
	int n;
	cin >> n;
	vector<vector<char>> graph(n, vector<char>(n));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> graph[i][j];
		}
	}
	int result = countConnectedPairs(graph);
	cout << result << endl;
	return 0;
}




//int main() {
//	int n;
//	cin >> n;
//	//输入
//	vector<vector<char>> graph(n);
//	for (int i = 0; i < n; ++i)
//	{
//		graph[i].resize(n);
//	}
//	for (int i = 0; i < n; ++i) {
//		for (int j = 0; j < n; ++j) {
//			cin >> graph[i][j];
//		}
//	}
//
//	vector<vector<char>> reach = graph;
//	//选择k为中间点
//	for (int k = 0; k < n; ++k) {
//		//使用i、j来访问矩阵，来构造可到达矩阵
//		for (int i = 0; i < n; ++i) {
//			for (int j = 0; j < n; ++j) {
//				//i经过中间点k能到达j
//				if (reach[i][k] && reach[k][j]) {
//					reach[i][j] = 1;
//				}
//			}
//		}
//	}
//
//	//计算总连通数
//	int count = 0;
//	for (int i = 0; i < n; ++i) {
//		for (int j = 0; j < n; ++j) {
//			if (reach[i][j]) {
//				count++;
//			}
//		}
//	}
//
//	cout << count << endl;
//	return 0;
//}


//1
//7 - 1 图的存储 - 邻接表
//分数 15
//作者 唐艳琴
//单位 中国人民解放军陆军工程大学
//输出给定图的邻接表。
/// <summary>
/// //////////////////////////////////////////////////
/// </summary>
struct Node
{
	int _i;
	list<int> _lis;

	Node(int i = 0)
		:_i(i)
	{

	}
};
//输出给定图的邻接表。
int main1()
{
	int N, M, S, prev, next;
	cin >> N >> M >> S;
	vector<Node> v(N);

	for (int i = 0; i < N; ++i)
	{
		v[i]._i = i;
	}

	for (int i = 0; i < M; ++i)
	{
		cin >> prev >> next;

		if (S == 1)
		{
			v[prev - 1]._lis.push_front(next - 1);
		}
		else
		{
			v[prev - 1]._lis.push_front(next - 1);
			v[next - 1]._lis.push_front(prev - 1);
		}

	}


	for (int i = 0; i < N; ++i)
	{
		cout << v[i]._i << ": ";
		for (int e : v[i]._lis)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	return 0;
}